from typing import List


class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        n = len(slices)
        m = n // 3

        # 情况1：选择第1个（不可以选最后一个）
        dp1 = [[0] * (m + 1) for _ in range(n - 1)]
        dp1[0][1] = slices[0]
        dp1[1][1] = max(slices[0], slices[1])
        for i in range(1, n - 1):
            for j in range(1, m + 1):
                dp1[i][j] = max(slices[i] + dp1[i - 2][j - 1], dp1[i - 1][j])

        # 情况1：不选第1个（可以选最后一个）
        dp2 = [[0] * (m + 1) for _ in range(n)]
        dp2[1][1] = slices[1]
        dp2[2][1] = max(slices[1], slices[2])
        for i in range(1, n):
            for j in range(1, m + 1):
                dp2[i][j] = max(slices[i] + dp2[i - 2][j - 1], dp2[i - 1][j])

        return max(dp1[-1][-1], dp2[-1][-1])


if __name__ == "__main__":
    print(Solution().maxSizeSlices(slices=[1, 2, 3, 4, 5, 6]))  # 10
    print(Solution().maxSizeSlices(slices=[8, 9, 8, 6, 1, 1]))  # 16
    print(Solution().maxSizeSlices(slices=[4, 1, 2, 5, 8, 3, 1, 9, 7]))  # 21
    print(Solution().maxSizeSlices(slices=[3, 1, 2]))  # 3
